package acm.力扣391周赛;

import org.junit.Test;

/**
 * 分治思想
 * https://leetcode.cn/contest/weekly-contest-391/problems/count-alternating-subarrays/
 */
public class 交替子数组计数 {
    int[] nums;
    static long[] one = {1, 1, 1};

    public long countAlternatingSubarrays(int[] nums) {
        this.nums = nums;
        return fun(0, nums.length - 1)[0];
    }

    /**
     * 0位置返回结果，1位置返回左侧有多少个不同的，2位置返回右侧有多少个不同的
     * @return
     */
    public long[] fun(int s, int e) {
        if (s == e) return one.clone();
        int le = s + e >> 1;
        int rs = le + 1;
        long[] left = fun(s, le);
        long[] right = fun(rs, e);
        long[] res = new long[3];
        if (nums[le] == nums[rs]) {
            res[0] = left[0] + right[0];
            res[1] = left[1];
            res[2] = right[2];
        } else {
            res[0] = left[0] + right[0] + left[2] * right[1];
            int pre = nums[s];
            int i = s + 1;
            while (i <= e && pre != nums[i]) {
                pre = nums[i];
                i++;
            }
            res[1] = i - s;
            pre = nums[e];
            i = e - 1;
            while (i >= s && pre != nums[i]) {
                pre = nums[i];
                i--;
            }
            res[2] = e - i;
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = {1, 0, 1, 1};
        long res = countAlternatingSubarrays(nums);
        System.out.println(res);
    }
}
